#include "avlTree.h"
#include <stdlib.h>
#include "logger.h"
AvlTree MakeEmpty(AvlTree T)
{
    if (T)
    {
        MakeEmpty(T->Left);
        MakeEmpty(T->Right);
        free(T);
    }
    return NULL;
}

Position Find(ElementType X, AvlTree T)
{
    if (!T)
        return NULL;
    if (X < T->Element)
        return Find(X, T->Left);
    else if (X > T->Element)
        return Find(X, T->Right);
    else
        return T;
}

static int Height(Position P)
{
    if (!P)
        return -1;
    else
        return P->Height;
}

static int MAX(int a, int b)
{
    return a > b ? a : b;
}

static Position SingleRotateWithLeft(Position P)
{
    Position P1 = P->Left;
    P->Left = P1->Right;
    P1->Right = P;
    P->Height = MAX(Height(P->Left), Height(P->Right)) + 1;
    P1->Height = MAX(Height(P1->Left), P->Height) + 1;
    return P1;
}
static Position SingleRotateWithRight(Position P)
{
    Position P1 = P->Right;
    P->Right = P1->Left;
    P1->Left = P;
    P->Height = MAX(Height(P->Left), Height(P->Right)) + 1;
    P1->Height = MAX(Height(P->Right), P->Height) + 1;
    return P1;
}
static Position DoubleRotateWithLeft(Position P)
{
    P->Left = SingleRotateWithRight(P->Left);
    return SingleRotateWithLeft(P);
}
static Position DoubleRotateWithRight(Position P)
{
    P->Right = SingleRotateWithLeft(P->Right);
    return SingleRotateWithRight(P);
}
//插入可能会导致破坏平衡二叉查找树的性质，因此需要通过旋转来保持平衡
AvlTree Insert(ElementType X, AvlTree T)
{
    //如果T为空，则证明找到插入位置了
    if (!T)
    {
        T = malloc(sizeof(*T));
        if (!T)
            FatalError("Out of space");
        T->Left = T->Right = NULL;
        T->Height = 0;
        T->Element = X;
    }
    else if (X < T->Element)
    {
        T->Left = Insert(X, T->Left);
        if (Height(T->Left) - Height(T->Right) == 2)
            if (X < T->Left->Element)
                //左左，单旋转
                T = SingleRotateWithLeft(T);
            else
                //左右，双旋转
                T = DoubleRotateWithLeft(T);
    }
    else if (X > T->Element)
    {
        T->Right = Insert(X, T->Right);
        if (Height(T->Right) - Height(T->Left) == 2)
            if (X > T->Right->Element)
                //右右，单旋转
                T = SingleRotateWithRight(T);
            else
                //右左，双旋转
                T = DoubleRotateWithRight(T);
    }
    else
        T->Deleted = 0;
    T->Height = MAX(Height(T->Left), Height(T->Right)) + 1;
    return T;
}

AvlTree Delete(ElementType X, AvlTree T)
{
    if (!T)
        return NULL;
    if (X < T->Element)
        T->Left = Delete(X, T->Left);
    else if (X > T->Element)
        T->Right = Delete(X, T->Right);
    else
        T->Deleted = 1;
    return T;
}

static void Print(AvlTree T, int Depth, int Right)
{
    if (!T)
        return;

    for (int i = 0; i < Depth; i++)
        printf(" ");
    printf("%d:%s", T->Element, Right ? "右" : "左");
    if (T->Deleted)
        printf("-del");
    printf("\n");

    Print(T->Left, Depth + 1, 0);
    Print(T->Right, Depth + 1, 1);
}

void PrintTree(AvlTree T)
{
    Print(T, 0, 0);
}
